工作隨筆:
今天突然意識到，面試時被騙了欸！
這兩天做的專案覺得窒礙難行，應該沒有可行的解決方案。
正在焦慮剛進來OKR就達成不了該怎辦呢～
突然想到當時面試時
主管: 還有什麼問題嗎？
我: 我對你剛剛介紹的專案蠻有興趣的，可以分享ooxx你們打算怎麼解決嗎，直覺上蠻難做到的欸。
主管: 我們會根據xxyy這樣解決
然後，今天突然意識到這個ooxx，就是我們這組的OKR，昨天開始啟動調研。
(大哥我三十幾天前面試的欸，你不是告訴我你們有解決方案了)
被騙了 氣死！
好吧繼續刷題=.=
Q: https://leetcode.com/problems/largest-multiple-of-three/description/
class Solution {
public String largestMultipleOfThree(int[] digits) {
int[] mod1 = new int[] {1, 4, 7, 2, 5, 8};
int[] mod2 = new int[] {2, 5, 8, 1, 4, 7};
int[] count = new int[10];
int sum = 0;
for (int digit : digits) {
count[digit]++;
sum += digit;
}
while (sum % 3 != 0) {
if (sum % 3 == 1) {
for (int number : mod1) {
if (count[number] != 0) {
count[number]--;
sum -= number;
break;
}
}
} else {
for (int number : mod2) {
if (count[number] != 0) {
count[number]--;
sum -= number;
break;
}
}
}
}
final StringBuilder sb = new StringBuilder();
for (int i = 9;i >= 0;i--) {
while (count[i] > 0) {
count[i]--;
sb.append(Character.toString('0' + i));
}
}
String ans = sb.toString();
if (ans.length() > 1 && ans.charAt(0) == '0') {
return "0";
}
return ans;
}
}
Q: https://leetcode.com/problems/jump-game-vii/description/
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
if(s == null || s.length() == 0) return false;
int n = s.length();
if(s.charAt(0) == '1' || s.charAt(n - 1) == '1') return false;
boolean[] dp = new boolean[n];
dp[0] = true;
int start = 0;
int end = 0;
for(int i = 0; i < n; i++){
if(!dp[i]) {
continue;
}
start = Math.max(end + 1, i + minJump);
end = Math.min(n - 1, i + maxJump);
for(int j = start; j <= end; j++){
if(s.charAt(j) == '0'){
dp[j] = true;
}
}
if(dp[n - 1]) return true;
}
return dp[n-1];
}
}
Q: https://leetcode.com/problems/count-number-of-texts/description/
/**
dp[x] -> x length max count number
for any string s we can see it like 0 ...... s.length()-2 s.length() - 1
for 2 3 4 5 6 8 click 1 ~ 3 times have a char so when pressedKeys.charAt(x) == {1,2,3,4,5,6,8} dp[x] = dp[x-1] + dp[x-2] + dp[x-3]
for 7 9 click 1 ~ 4 times have a char so when pressedKeys.charAt(x) == {7, 9} dp[x] = dp[x-1] + dp[x-2] + dp[x-3] + dp[x-4];
*/
class Solution {
public int countTexts(String pressedKeys) {
int maxCount = 1000000007;
int n = pressedKeys.length();
int[] dp = new int[n + 1];
dp[0] = 1;
char c = 'a';
int count = 0;
for (int i = 1;i <= n;i++) {
if (c != pressedKeys.charAt(i - 1)) {
count = 0;
}
c = pressedKeys.charAt(i - 1);
if (count > 0) {
if ((c == '1' || c == '2' || c == '3' || c == '4' || c == '5' || c == '6' || c == '8') && count < 3) {
count++;
} else if ((c == '7' || c == '9') && count < 4) {
count++;
}
} else {
count = 1;
}
int j = 1;
int sum = 0;
while(j <= count && i - j >=0) {
sum += dp[i - j];
sum = sum % maxCount;
j++;
}
dp[i] = sum;
}
return dp[n];
}
}
Q: https://leetcode.com/problems/minimum-flips-in-binary-tree-to-get-result/description/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Map<TreeNode, Integer> memo20 = new HashMap<>();
private Map<TreeNode, Integer> memo21 = new HashMap<>();
private Map<TreeNode, Integer> memo30 = new HashMap<>();
private Map<TreeNode, Integer> memo31 = new HashMap<>();
private Map<TreeNode, Integer> memo40 = new HashMap<>();
private Map<TreeNode, Integer> memo41 = new HashMap<>();
private Map<TreeNode, Integer> memo50 = new HashMap<>();
private Map<TreeNode, Integer> memo51 = new HashMap<>();
public int minimumFlips(TreeNode root, boolean result) {
if (root == null) {
return 0;
}
if (root.val == 2) {
if (result) {
if (memo21.containsKey(root)) {
return memo21.get(root);
}
int min = Math.min(minimumFlips(root.left, true), minimumFlips(root.right, true));
memo21.put(root, min);
return min;
} else {
if (memo20.containsKey(root)) {
return memo20.get(root);
}
int min = minimumFlips(root.left, false) + minimumFlips(root.right, false);
memo20.put(root, min);
return min;
}
} else if (root.val == 3) {
if (result) {
if (memo31.containsKey(root)) {
return memo31.get(root);
}
int min = minimumFlips(root.left, true) + minimumFlips(root.right, true);
memo31.put(root, min);
return min;
} else {
if (memo30.containsKey(root)) {
return memo30.get(root);
}
int min = Math.min(
Math.min(
minimumFlips(root.left, true) + minimumFlips(root.right, false),
minimumFlips(root.left, false) + minimumFlips(root.right, true)
),
minimumFlips(root.left, false) + minimumFlips(root.right, false));
memo30.put(root, min);
return min;
}
} else if (root.val == 4) {
if (result) {
if (memo41.containsKey(root)) {
return memo41.get(root);
}
int min = Math.min(
minimumFlips(root.left, true) + minimumFlips(root.right, false),
minimumFlips(root.left, false) + minimumFlips(root.right, true));
memo41.put(root, min);
return min;
} else {
if (memo40.containsKey(root)) {
return memo40.get(root);
}
int min = Math.min(
minimumFlips(root.left, true) + minimumFlips(root.right, true),
minimumFlips(root.left, false) + minimumFlips(root.right, false));
memo40.put(root, min);
return min;
}
} else if (root.val == 5) {
if (result) {
if (memo51.containsKey(root)) {
return memo51.get(root);
}
int min;
if (root.left == null) {
min = minimumFlips(root.right, !result);
} else {
min = minimumFlips(root.left, !result);
}
memo51.put(root, min);
return min;
} else {
if (memo50.containsKey(root)) {
return memo50.get(root);
}
int min;
if (root.left == null) {
min = minimumFlips(root.right, !result);
} else {
min = minimumFlips(root.left, !result);
}
memo50.put(root, min);
return min;
}
}
if (result) {
return root.val == 1 ? 0 : 1;
}
return root.val == 0 ? 0 : 1;
}
}
Q: https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/description/
class Solution {
public int maximumSum(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int[] b = new int[n];
int maxSum = nums[0];
f[0] = nums[0];
for (int i = 1; i < n; i++) {
f[i] = Math.max(nums[i], f[i - 1] + nums[i]);
maxSum = Math.max(maxSum, f[i]);
}
b[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
b[i] = Math.max(nums[i], b[i + 1] + nums[i]);
}
for (int i = 1; i < n - 1; i++) {
maxSum = Math.max(maxSum, f[i - 1] + b[i + 1]);
}
return maxSum;
}
}
iThome鐵人賽
看影片追技術